/**
 * 项目名称: Topic_11.cpp
 * 项目路径: study/DataStructure/刷题/一轮/第十一天 数组+双指针
 * 编辑时间: 2024年09月12日20时14分04秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

//class Solution {
//public:
//    int maxArea(vector<int>& height) {
//        int maxVal = 0;
//        int current = 0;
//        int next = 0;
//        for(int i = 0 ; i < height.size() - 1; i++)
//        {
//            next = i+1;
//            int val_1 = min(height[next],height[current])*(next - i);
//            int val_2 = min(height[i],height[next]);
//            if(val_2 > val_1)
//            {
//                current++;
//                maxVal = val_2;
//            }
//            if(val_1 >= maxVal)maxVal = val_1;
//        }
//        return maxVal;
//    }
//};
/**
 * 典型双指针算法,两个指针分别只在数组两侧,从两侧不断向中间靠拢,
 * 每次移动较小的那个高度,必然会有一个先到达最优解,
 * 此时,不妨设左边先到达最优解,
 * 那必然,右边是小于左边,不断向左移动.
 * 反证法:
 *  假设右边高度大于左边,如果右边向左边移动,必然会导致面积减小
 *  由此,必是左边的向右移动,这与原假设矛盾,必然不对
 *  因此,原假设成立
 */
class Solution {
public:
    int maxArea(vector<int> &height) {
        int pre = 0;
        int next = height.size()-1;

        int maxVal = 0;
        while (pre < next)
        {
            if(height[pre] < height[next])
            {
                maxVal = max(maxVal,height[pre]*(next - pre));
                pre++;
            }
            else
            {
                maxVal = max(maxVal,height[next]*(next - pre));
                next--;
            }
        }
        return maxVal;
    }
};